//从前序与中序遍历序列构造二叉树
//https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/?envType=study-plan-v2&envId=top-interview-150
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> _preorder;
    vector<int> _inorder;
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) 
    {
        _preorder = preorder;
        _inorder = inorder;
        return dfs(0,preorder.size() - 1,0,preorder.size() - 1);
    }

    //构建树并返回
    TreeNode* dfs(int begin1, int end1, int begin2, int end2)
    {
        if(begin1 > end1) return nullptr;
        //找根
        int val = _preorder[begin1];
        TreeNode* root = new TreeNode(val);
        int pos = 0;

        for(int i = begin2; i <= end2; i++)
        {
            if(_inorder[i] == val)
            {
                pos = i;
                break;
            }
        }
        
        //计算左节点有多少个
        int lsum = pos - begin2;
        //计算右节点有多少个
        int rsum = end2 - pos;
    
        root->left = dfs(begin1 + 1, begin1 + lsum, begin2,pos - 1);
        root->right = dfs(begin1 + lsum + 1, begin1 + lsum + rsum, pos + 1,end2);
        return root;
    }
};